Побудова найкоротшого шляху у графі

Інформація про навчальний заклад

ВУЗ:
Вінницькій національний технічний університет
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Не вказано

Інформація про роботу

Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології

Частина тексту файла

Міністерство освіти і науки Вінницький національний технічний університет Інститут Інформаційних Технологій та Комп’ютерної Інженерії Кафедра комп’ютерних наук Лабараторна робота № 9-10 з дисципліни: Дискретна математика. Тема: Побудова найкоротшого шляху у графі м.Вінниця 2013 Мета роботи: набути навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. Порядок виконання роботи: Проаналізувати хвильовий алгоритм і алгоритм Дейкстри на конкретному прикладі згідно з індивідуальним завданням. Розробити схему алгоритму побудови найкоротшого шляху в зваженому графі за хвильовим алгоритмом і алгоритмом Дейкстри. Розробити програму, яка реалізує дані алгоритму. Для заданого варіанту привести результати тестування розробленої програми. Розробити інструкцію користувача. Оформити звіт і зробити висновки за результатами роботи. Завдання №14 / Блок – схема програми що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. Результати виконання програми. / Рисунок 2. Висновок: В ході виконання лабораторної роботи було набуто навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. , у ході роботи було представлено результати тестування програми яку розроблено на мові С++. Додаток(лістинг програми, що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри). #include <iostream> #include <conio.h> #pragma hdrstop #pragma argsused #include <fstream> #include <algorithm> #include <vector> #include <iostream> using namespace std; #define VERTEXES 13 int v; int main(int argc, char* argv[]) { setlocale(LC_ALL,""); char arr[13]={'x0','x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7', 'x8', 'x9', 'x10','x11','x12'}; int infinity=1000; // Бесконечность int p= VERTEXES; // Количество вершин в графе int s,i,j; // Номер исходной вершины int g; // Номер конечной вершины cout<<"Введите s: ";cin>>s; // Номер может изменяться от 0 до p-1 cout<<"Введите g: ";cin>>g; printf(" "); for(int q=0; q<13; q++) printf(" x%d",q); printf("\n"); for(i=0; i<13; i++) { printf("x%d",i); if(i<10)printf(" "); for(j=0; j<13; j++) { printf(" %d ", a[i][j]); if(j>9)printf(" "); } printf("\n");} int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины, // x[i]=0 - еще не найден кратчайший путь в i-ю вершину, // x[i]=1 - кратчайший путь в i-ю вершину уже найден int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине // на кратчайшем пути // Инициализируем начальные значения массивов int u; // Счетчик вершин for (u=0;u<p;u++) { t[u]=infinity; //Сначала все кратчайшие пути из s в i //равны бесконечности x[u]=0; // и нет кратчайшего пути ни для одной вершины } h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует t[s]=0; // Кратчайший путь из s в s равен 0 x[s]=1; // Для вершины s найден кратчайший путь v=s; // Делаем s текущей вершиной while(1) { // Перебираем все вершины, смежные v, и ищем для них кратчайший путь for(u=0;u<p;u++) { if(a[v][u]==0)continue; // Вершины u и v несмежные if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не //найден кратчайший путь // и новый путь в u короче чем //старый, то { t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в //массив t и h[u]=v; //запоминаем, что v->u часть кратчайшего //пути из s->u } } // Ищем из всех длин некратчайших путей самый ...
Антиботан аватар за замовчуванням

06.02.2014 01:02

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини